/**
 * 312. 戳气球
 * https://leetcode-cn.com/problems/burst-balloons/
 */

// /**
//  * @param {number[]} nums
//  * @param {number} left
//  * @param {number} right
//  * @param {number[][]} memory
//  */
// function intervalMax(nums, left, right, memory) {
//   if (left >= right - 1) {
//     return 0;
//   }
//   if (memory[left][right] >= 0) {
//     return memory[left][right];
//   }
//   let max = 0;
//   for (let i = left + 1; i < right; i += 1) {
//     max = Math.max(max, intervalMax(nums, left, i, memory) + nums[left] * nums[i] * nums[right] + intervalMax(nums, i, right, memory));
//   }
//   memory[left][right] = max;
//   return max;
// }
//
// /**
//  * 记忆法
//  * @param {number[]} nums
//  * @return {number}
//  */
// function maxCoins(nums) {
//   nums = [1, ...nums, 1];
//   const memory = new Array(nums.length);
//   for (let i = 0; i < nums.length; i += 1) {
//     memory[i] = new Array(nums.length).fill(-1);
//   }
//   return intervalMax(nums, 0, nums.length - 1, memory);
// }

/**
 * 动态规划
 * @param {number[]} nums
 * @return {number}
 */
function maxCoins(nums) {
  nums = [1, ...nums, 1];
  const dp = new Array(nums.length);
  for (let i = 0; i < nums.length; i += 1) {
    dp[i] = new Array(nums.length).fill(0);
  }
  for (let k = 2; k < nums.length; k += 1) {
    for (let i = k - 2; i >= 0; i -= 1) {
      let max = 0;
      for (let j = i + 1; j < k; j += 1) {
        max = Math.max(max, dp[i][j] + nums[i] * nums[j] * nums[k] + dp[j][k]);
      }
      dp[i][k] = max;
    }
  }
  return dp[0][nums.length - 1];
}

console.log(maxCoins([3, 1, 5, 8]) === 167);
console.log(maxCoins([1, 5]) === 10);
console.log(maxCoins([5]) === 5);
